1. Field of the Invention
The present invention relates to a system and process for the creation, manipulation and perspective display of complex scenes having one or more three-dimensional objects. More particularly, the invention relates to systems and processes of the above-described type which remove hidden lines and surfaces from the display of three-dimensional scenes on a two-dimensional view reference plane of a display device.
2. Description of the Prior Art
Computer graphics systems display perspective views of complex scenes made up of one or more three-dimensionl objects in a two-dimensional view reference plane of a display device such as a video monitor. The basic apparatus and processes for the display of three-dimensional scenes in a view reference plane of a two-dimensional display device are well known, as exemplified by descriptions in textbooks such as "Fundamentals of Interactive Computer Graphics," by J. D. Foley and A. VanDam, Addison-Wesley Publishing Co., 1982.
Several basic processes are required in the creation and display of a three-dimensional scene as a perspective view on the view reference plane of a display device. In the first place, the scene to be perspectively displayed must be mathematically represented in three-dimensional spatial coordinates to permit its transformation by matrix calculations into a mathematical representation of a perspective view referenced with respect to the view reference plane of the display device. One known way of mathematically representing a three-dimensional scene is to define it as a plurality of objects each having a plurality of planar surfaces such as triangles or tetrahedrons each defined by a listing of its vertices. The number of surfaces required to mathematically represent any scene containing a plurality of objects is a function of the complexity of the scene to be displayed and the degree of required resolution. With reference to FIG. 1 of the drawings, a cube 10 may be mathematically represented by six faces each defined by four of the eight total vertices. More complex objects require proportionally more surfaces and a greater number of vertices. A description of the process of mathematically representing a three-dimensional scene by polygons defined by vertices is described on pages 295-301 of "Tutorial: Computer Graphics," by Kellogg S. Booth, IEEE Catalog No. EHO 147-9, 1979.
The transformation of the three-dimensional mathematical representation of the scene to be displayed to a two-dimensional mathematical perspective referenced to the view reference plane is known as perspective transformation. The complete transformation from the three-dimensional "object" coordinate system to a two-dimensional perspective coordinate system having depth referenced with respect to the view reference plane is performed by two separate matrix transformations. The first coordinate transformation expresses the location of the objects defining the scene relative to the world coordinate system. The second coordinate transformation applies a perspective mapping onto the view reference plane. The foregoing transformations are known and described in detail in "Tutorial: Computer Graphics," supra, on pages 300-303, and in Chapter 8 "Fundamentals of Interactive Computer Graphics", supra.
The removal of hidden surfaces and lines from the scene to be produced is necessary for the creation of a realistic perspective view. Hidden surfaces and lines are those surfaces and lines which are obscured by parts of the scene located closer to the view reference plane. The matrix transformations of a scene into a mathematically defined perspective view transforms all of the lines and surfaces of the scene which are present. Display of the mathematically defined perspective view without hidden surface and line removal creates an unrealistic perspective view. With reference to FIG. 1 with the view reference plane considered to be the plane of the drawing containing FIG. 1, cube 10 contains three hidden lines and three hidden surfaces which are respectively identified by the dotted line segments 6-4, 3-4, and 4-1 and the surfaces defined by vertices 3456, 1234, and 1467. The subject matter of the present invention pertains to the generation of a perspective view of object which typically are much more complex than cube 10 with the removal of hidden surfaces and hidden lines from a perspective display.
Algorithms are known in the prior art for the removal of hidden surfaces and hidden lines. The "Tutorial: Computer Graphics", supra, contains a description of ten hidden surface removal algorithms. Algorithms are described therein on pages 324-326 which determine the visibility of surfaces of different depth as defined with respect to the view reference plane along a single line of scanning of a display device. These line algorithms compare the depth of line segments from the various faces which are projected from different depths on the z axis to an intersection along the x direction of scanning to cause the display of only those line segments which are disposed closest to the view reference plane. U.S. Pat. Nos. 3,736,564, 3,621,214 and 3,602,702 further describe known hidden surface removal algorithms. Scan line algorithms are also discussed in section 15.6 of the "Fundamentals of Interactive Computer Graphics", supra.
An additional algorithm for the removal of hidden surfaces is the z-buffer algorithm which is described in section 15.5 of the "Fundamentals of Interactive Computer Graphics", supra. This algorithm stores in memory the depth values of each pixel of a frame along the lines of scanning. This algorithm, while simple in programming comcept, requires substantial computer time and memory to implement because each pixel of each polygon is stored in the depth buffer and compared with the pixels of all of the other polygons to determine the pixels lying closest to the view reference plane.
An important aspect of the implementation of a hidden surface algorithm in a computer graphics system is the time required to perform the mathematical processing necessary to identify those surfaces which should be displayed and those surfaces which should be discarded as hidden surfaces. All hidden surface algorithms require a comparison of information from a potentially visible area, scan line, or point basis within a surface with the corresponding area, scan line, or points of other potentially visible surfaces. The computation time required for a computer to perform the necessary comparisons and sorting depends on the number of records to be processed, the algorithm used to perform the comparisons and sorts, and the statistical properties of the records being compared and sorted. The precise properties of sorting and comparing techniques are of tremendous importance in the overall time required to implement a hidden surface algorithm. Certain techniques require more storage space than others and some lend themselves to fast hardware implementation more easily than others.
Scan line algorithms compute the intersection of each surface of the three-dimensional scene which is to be perspectively illustrated on the view reference plane with the x axis of line to be scanned. The line segments resulting from the intersection of the view reference plane are called segments.
Scan line algorithms are based upon the coherent property of segments in which the variation from scan line to scan line is statistically small. The creation of line segments simplifies the hidden surface problem to a two-dimensional problem of segments measured by the x and z coordinates given the fact that the y coordinate is a constant. Elimination of the variation of the y coordinate requires simpler computations than those which are required in three-dimensions for area algorithms for removing hidden surfaces.
The Watkins algorithm, as described on pages 324-326 of the "Tutorial: Computer Graphics", supra, and U.S. Pat. No. 3,736,564, initially determines the beginning and end points of the intersection of each segment with the x axis of the line of scanning. When more than one segment is determined to have at least a partially overlapping beginning and end points along the x axis, the algorithm subdivides the initial segments in half repeatedly until either there is no overlap on the x axis or until the problem of determining which segment lies closest to the view reference plane becomes simple or approaches the limit of resolution of the overall system and therefore can be discarded. The Watkins algorithm requires extensive computation time to generate the list of sufficiently subdivided segments when highly complex scenes having many potentially visible faces are being procesed. Thus, Watkins algorithm has a progressively increasing computation time overhead as the complexity of the scenes to be displayed increases.